package features.advance.leetcode.array.easy;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 *  剑指 Offer 57. 和为s的两个数字
 *
 *  难度：简单
 *
 * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[2,7] 或者 [7,2]
 * 示例 2：
 *
 * 输入：nums = [10,26,30,31,47,60], target = 40
 * 输出：[10,30] 或者 [30,10]
 *
 *
 * 限制：
 *
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^6
 *
 * @author LIN
 * @date 2021-05-31
 */
public class Offer57 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public int[] twoSum(int[] nums, int target) {
                int left = 0, right = nums.length - 1;
                while (left < right) {
                    if (target - nums[right] == nums[left]) return new int[]{nums[left], nums[right]};
                    while(target - nums[right] < nums[left] && left < right) right--;
                    while(target - nums[right] > nums[left] && left < right) left++;
                }
                return new int[0];
            }
        };

        InputStream resourceAsStream = solution.getClass().getClassLoader().getResourceAsStream("\\57.txt");
        assert resourceAsStream != null;
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(resourceAsStream));
        StringBuilder sb = new StringBuilder();
        int[] nums = {};
        try{
            int i = -1;
            int tmp = 0;
            while ((i=bufferedReader.read())!=-1) {
                if(i != '[' & i!=']'){
                    if (i != ',') {
                        sb.append((char) i);
                    }else{
                        nums = Arrays.copyOf(nums, nums.length + 1);
                        nums[nums.length - 1] = Integer.parseInt(sb.toString());
                        sb = new StringBuilder();
                    }
                }
            }
            bufferedReader.close();
        }catch (Exception e){
            e.printStackTrace();
        }
        nums[nums.length - 1] = Integer.parseInt(sb.toString());
        int target = 1401327;
        long start = System.currentTimeMillis();
        int[] ints = solution.twoSum(nums, target);
        System.out.println(System.currentTimeMillis() - start);

        System.out.println(Arrays.toString(ints));
    }

    static class Solution{
        /**
         * 思路：双指针
         * 最大的加最小的都比target大，所以最大的数舍弃；最小的加最大的都比target小，所以最小的舍弃
         * @param nums
         * @param target
         * @return
         */
        public int[] twoSum(int[] nums,int target){
            int i = 0, j = nums.length - 1;
            while(i < j) {
                // 防止两个数相加之后太大超类型范围，导致数据溢出
                if(target - nums[i] > nums[j]){
                    i++;
                }else if(target - nums[i] < nums[j]){
                    j--;
                }else{
                    return new int[] { nums[i], nums[j] };
                }
            }
            return new int[0];
        }
    }
}
